package chapter01;

public class Search {
    //二分法
    /**
     * 数组经过旋转 二分后一定能分成两部分 一部分一定有序 另一部分可能有序也可能一部分有序
     * 选取前半部分判断
     *    1）前半部分有序 nums[left]<=nums[mid] 小于等于是为了涵盖只剩下两个元素时判断
     *       a.nums[left]<=target&&target<nums[mid]  target位于[left,mid-1]
     *       b.否则target位于[mid+1,right]
     *    2)否则前半部分无序
     *       a.nums[mid]<target&&target<=nums[right]  巧用后半部分有序判断 target位于[mid+1,right]
     *       b.否则 target位于[left,mid-1]
     */
    public int search(int[] nums, int target) {
        if(nums==null||nums.length<1){
            return -1;
        }
        int length=nums.length;
        if(length==1){
            return target==nums[0]?0:-1;
        }
        int left=0,right=length-1;
        while (left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target){
                return mid;
            }
            //前半部分有序 <=为了防止只剩下两个数据无法判断
            if(nums[left]<=nums[mid]){
                if (nums[left]<=target&&target<nums[mid]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }else{
                if(nums[mid]<target&&target<=nums[right]){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }
        }
        return -1;
    }
}
